home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 10 - 1994 / 10.05 May 94 / Programmer’s Challenge / bitmap.c
Encoding:
C/C++ Source or Header  |  1994-03-11  |  10.0 KB  |  363 lines  |  [TEXT/KAHL]
  1. /* March 94 Challenge - BitMapToText
  2. ** by Bob Boonstra
  3. **
  4. ** Strategy
  5. **
  6. **   The problem states that "the smallest detail in the
  7. **     input image [will] be roughly equal to or larger than
  8. **     a single character of the given font and font size.
  9. **   Therefore, this solution attempts only to match the
  10. **     number of bits set in a given character size piece
  11. **     of the image with the number of bits set in the
  12. **     character chosen to represent that piece of the 
  13. **     image.
  14. **   The strategy is to:
  15. **     (1) draw the characters from 32 to 127 in an 
  16. **         offscreen bitmap.
  17. **     (2) sort the characters in order of increasing 
  18. **         number of bits set
  19. **     (3) precalculate a mapping from pixel density to
  20. **         output characters
  21. **     (4) loop thru the character size chunks of the image,
  22. **         count the number of bits set, and output the
  23. **         corresponding character.
  24. **
  25. ** Assumptions
  26. **   Width of characters is assumed to be <=32 pixels
  27. **     (reasonable for (6-24 point mono font)
  28. **   No assumption that actual height of font <= 24;
  29. **     ascent+descent+leading may exceed point size
  30. **     Ref NIM: Text pg 4-11
  31. **   bitMapPtr->rowBytes * (font height) assumed < 32K
  32. */
  33.  
  34. #include <stdio.h>
  35.  
  36. #pragma options (honor_register, !assign_registers)
  37.  
  38. #define uchar unsigned char
  39. #define ushort unsigned short
  40. #define ulong unsigned long
  41.  
  42. #define EOL 0x0d
  43. #define kErr 1
  44. #define kFirstChar 32
  45. #define kLastCharPlus1 128
  46. #define kNumChars (kLastCharPlus1-kFirstChar)
  47. #define kBytesPerBMChar sizeof(long)
  48. #define kMaxCharWidth (8*kBytesPerBMChar)
  49. #define kCharRowBytes 384
  50. #define kBitsPerChunk 32
  51. #define kMaxCharVals 512
  52.  
  53. #define DoSetMem(addr,sz,val)                            \
  54.   { register long *p = (long *)addr;                     \
  55.     register short count = sz;                           \
  56.     do *p++=val; while (--count);                        \
  57.   }
  58.  
  59. // Macro BitCount(x,count) increments count for each bit 
  60. //   in x set to 1.
  61. // WARNING:  the expression (x=x--&x) in the BitCount 
  62. //   macro is not portable, because the order of evaluation
  63. //   is undefined, but it generates correct fast code
  64. //   for (x=x&(x-1)) in THINK C.
  65. //   Non-portable code is BAD FOR YOU, except where speed
  66. //   is very important, like in this Challenge.
  67. #define BitCount(x,initVal,count)  \
  68.   if (x=initVal) do ++count; while (x = x--&x);
  69.  
  70. ushort lineHeight,charWid;
  71. FontInfo fInfo;
  72.  
  73. short InitOffscreenBitMap(GrafPort *charPtr)
  74. {
  75. //
  76. // Initialize font information
  77. //
  78.     Point scalePt = {1,1};
  79.     ulong numBytes;
  80.     GetFontInfo(&fInfo);
  81.     lineHeight = fInfo.leading+fInfo.ascent+fInfo.descent;
  82.     charPtr->pnLoc.v = lineHeight -fInfo.descent;
  83. //
  84. // Initialize GrafPort and bitmap storage 
  85. //
  86.     numBytes = lineHeight*kCharRowBytes;
  87.     if (0 == (charPtr->portBits.baseAddr = 
  88.                 (QDPtr)NewPtr( numBytes )))
  89.       return kErr;
  90.     DoSetMem(charPtr->portBits.baseAddr,
  91.                                   numBytes/sizeof(long),0);
  92.     charPtr->portBits.rowBytes = kCharRowBytes;
  93.     charPtr->portBits.bounds.top = 0;
  94.     charPtr->portBits.bounds.left = 0;
  95.     charPtr->portBits.bounds.bottom = lineHeight;
  96.     charPtr->portBits.bounds.right = kCharRowBytes*8;
  97.     RectRgn(charPtr->visRgn,&charPtr->portBits.bounds);
  98.     charWid = StdTxMeas(1,"W",&scalePt,&scalePt,&fInfo);
  99. /*if (charWid != fInfo.widMax) DebugStr("\p bad wid");*/
  100.     if (kBytesPerBMChar*8 < charWid) return kErr;
  101.     return 0;
  102.   }
  103.  
  104. //
  105. // Draw the characters of the given font into an offscreen
  106. // bitmap.
  107. //
  108. void  DrawTheChars(GrafPtr charPort)
  109. { 
  110.   register Point scalePt = {1,1};
  111.   register short hPos = kMaxCharWidth-charWid;
  112.   register short count;
  113.   uchar chVal = kFirstChar;
  114.   count = kNumChars; do {
  115.     charPort->pnLoc.h = hPos;
  116.     StdText(1,&chVal,scalePt,scalePt);
  117.     hPos += kMaxCharWidth;
  118.     ++chVal;
  119.   } while (--count);
  120. }
  121.  
  122. //
  123. // Calculate the number of bits set in each character, for 
  124. // subsequent use in comparing to a section of the bitmap.
  125. //
  126. void InitBitsSetArray(register char *p,register ushort *c)
  127. {
  128.   register short count;
  129.   p += (ushort)fInfo.leading*kCharRowBytes;
  130.   count = kNumChars; do {
  131.     register ushort bitcount=0;
  132.     register uchar *q = (uchar *)p;
  133.     register short vCount;
  134.     vCount = lineHeight-fInfo.leading; do {
  135.       register ulong row;       
  136.       BitCount(row,*(ulong *)q,bitcount);
  137.       q += kCharRowBytes;
  138.     } while (--vCount);
  139. //  Following line fudges the density value for characters
  140. //  to account for the fact that the most dense character
  141. //  is significantly less dense than a dark section of a
  142. //  bitmap.
  143.     bitcount += bitcount>>1;
  144.     *c++ = bitcount;
  145.     p += kBytesPerBMChar;
  146.   } while (--count);
  147. }
  148.  
  149. //
  150. // Sort the characters in order of increasing number of
  151. // bits set (density).
  152. //
  153. void SortBitsSetArray(register ushort *v, 
  154.                       register ushort *c)
  155. {
  156.   register ushort *x;
  157.   register ushort count,val,xVal,newVal;
  158. // Initialize sort order
  159.   count = kNumChars; val = 0; x=c; do {
  160.     *x++ = val;  ++val;
  161.   } while (--count);
  162. // Bidirectional exchange sort is good enough for this small
  163. // array
  164.   count = kNumChars-1;
  165.   x = c;
  166.   val = *(v+*c);
  167.   do {
  168.     ushort *saveC;
  169.     ushort saveCount;
  170.     xVal = *(c+1);
  171.     newVal = *(v+xVal);
  172.     if (val > /**x*/ newVal) {
  173. //    Swap pointers
  174.       *(c+1) = *c;   *c = xVal;
  175.       if (count < kNumChars-1) {
  176.         saveC=c+1;  saveCount=count;  val = *(v+*c); 
  177.         do {
  178.           xVal = *(c-1);  x = v+xVal;  newVal = *x;
  179.           if (val >= newVal) break;
  180.           *(c-1) = *c;  *c = xVal;   --c;
  181.         } while (++count < kNumChars-1);
  182.         count = saveCount;  c=saveC;  val = *(v+*c);
  183.       } else {
  184.         val = *(v+*c++);
  185.       }
  186.     } else {
  187.       val = newVal;  ++c;
  188.     }
  189.   } while (--count);
  190. }
  191.  
  192. //
  193. // Initialize a mapping from number of bits set in a
  194. // character-sized section of the bitmap to the character
  195. // used to represent that section.
  196. //
  197. void InitCharPointerArray(register ushort *v, 
  198.      register ushort *c, register ushort *p)
  199. {
  200.   register short count1,count2,count3;
  201.   register short currentVal;
  202.   count2 = kNumChars;
  203.   count1 = -1;
  204.   do {
  205.     currentVal = *(v+*c);
  206.     if (currentVal>count1) {
  207.       count3 = (ushort)(currentVal-count1)/2;
  208.       if (count3) do {
  209.         *p++=*(p-1);
  210.         if (++count1 >= kMaxCharVals) return;
  211.       } while (--count3);
  212.       do {
  213.         *p++=' '+*c;
  214.         if (++count1 >= kMaxCharVals) return;
  215.       } while (currentVal>count1);
  216.     }
  217.     ++c;
  218.   } while (--count2);
  219.   do {
  220.     *p++=*(p-1);
  221.   } while (++count1<kMaxCharVals);
  222. }
  223.  
  224. short BitMapToText(bitMapPtr,fontName,fontSize,outputFile)
  225. BitMap *bitMapPtr;
  226. Str255 fontName;
  227. unsigned short fontSize;
  228. FILE *outputFile;
  229. {
  230. GrafPort charPort;
  231. GrafPtr savePort;
  232.  
  233. //
  234. // bitsSet[x] is the number of bits set to 1 in the 
  235. //            representation of character ' '+x
  236. // sortedCharP[y]+' ' is the y-th character in order of
  237. //                    increasing number of bits set
  238. //
  239. ushort bitsSet[kNumChars],sortedCharP[kNumChars];
  240. //
  241. // charVals[c] is the character to be output for a character
  242. //             size piece of the bitmap with c bits set
  243. //
  244. ushort charVals[1+kMaxCharVals];
  245.  
  246. register ulong *q,*rowP;
  247. register short count,numBitsSet;
  248. register ulong mask;
  249.  
  250. register uchar *p;
  251. ulong origMask;
  252. ushort lineBytes;
  253. short rCnt,rowBytes,hPix,fontNum,theErr;
  254.  
  255.   GetFNum(fontName,&fontNum);
  256.   if (0 == fontNum) return (kErr);
  257.   if (!RealFont(fontNum,fontSize)) return (kErr);
  258.   GetPort(&savePort);
  259.   OpenPort(&charPort);
  260.   TextFont(fontNum);
  261.   TextSize(fontSize);
  262.   if (theErr = InitOffscreenBitMap(&charPort))
  263.     return theErr;
  264. //
  265. // Draw characters in bitmap.  Draws them one at a time
  266. // so we can align the characters within long words. 
  267. //
  268.   DrawTheChars(&charPort);
  269.   SetPort(savePort);
  270. //  
  271. // Init charVal array of characters to output.
  272. //
  273.   InitBitsSetArray(charPort.portBits.baseAddr,bitsSet);
  274.   SortBitsSetArray(bitsSet,sortedCharP);
  275.   InitCharPointerArray(bitsSet,sortedCharP,charVals);
  276. //
  277. //  Process bitMap.
  278. //
  279.   p = (uchar *)bitMapPtr->baseAddr;
  280.   rowBytes = bitMapPtr->rowBytes;
  281.   lineBytes = rowBytes*lineHeight;
  282.   rCnt = bitMapPtr->bounds.bottom - bitMapPtr->bounds.top;
  283.   hPix = bitMapPtr->bounds.right - bitMapPtr->bounds.left;
  284. //
  285. // Set a mask of charWid characters using a sign-extended
  286. // shift.
  287. //
  288.   origMask = mask = (ulong)
  289.            ((signed long)0x80000000>>(charWid-1));
  290. //
  291. //  Loop on rows of characters.
  292. //
  293.   do {
  294.     short numBits,bitsThisChunk,bitsToGo,hCnt;
  295.     rowP = (ulong *)p;
  296.     bitsThisChunk = kBitsPerChunk;
  297.     hCnt = hPix;
  298.     numBits = bitsToGo = charWid;
  299. //
  300. //  Loop on chars within current row.
  301. //
  302.     do {
  303. //
  304. //    Count bits set in current char.
  305. //
  306.       numBitsSet=0;
  307. //
  308. //    Loop on pixels in this chunk.
  309. //
  310.       do {
  311.         q = rowP;
  312.         count = lineHeight;
  313. //
  314. //      Count number of bits set in this chunk.
  315. //
  316.         do {
  317.           register ulong ch;
  318.           BitCount(ch,*q & mask,numBitsSet);
  319.           q = (ulong *)((uchar *)q + rowBytes);
  320.         } while (--count);
  321. //
  322. //  Continue processing current char if there are bitsToGo.
  323. //
  324.         if (0 == (bitsThisChunk -= numBits)) {
  325. //        Check for end of row.
  326.           if (hCnt < (bitsThisChunk=kBitsPerChunk))
  327.             bitsThisChunk = hCnt;
  328.           ++rowP;
  329.           if (bitsToGo-=numBits) {
  330.             if (bitsToGo > hCnt) bitsToGo = hCnt;
  331.             mask = origMask << (charWid - bitsToGo);
  332.             numBits = bitsToGo;
  333.           } else {
  334.             mask = origMask;
  335.             break;
  336.           }
  337.         } else if (numBits != charWid) {
  338.           mask = (origMask >> bitsToGo);
  339.           break;
  340.         } else {
  341.           mask >>= numBits;
  342.           break;
  343.         }
  344.       } while (true);  /* break if (0 == bitsToGo) */
  345.       numBits = bitsToGo = charWid;
  346.       if (numBits>bitsThisChunk) numBits=bitsThisChunk;
  347. //
  348. //  Select output character;
  349. //
  350.       if (numBitsSet<kMaxCharVals)
  351.         count = *(charVals+numBitsSet);
  352.       else count = *(charVals+kMaxCharVals);
  353.       putc(count,outputFile);
  354.     } while (0 < (hCnt-=charWid));
  355.     p += lineBytes;
  356.     putc(EOL,outputFile);
  357.     if (0 > rCnt) break;
  358.     if (0 > (rCnt-=lineHeight)) lineHeight += rCnt;
  359.     mask =  origMask;
  360.   } while (true);
  361.   return 0;
  362. }
  363.